from typing import List

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        self.dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        self.dp[0][0] = grid[0][0]
        for i in range(0, len(grid)):
            for j in range(0, len(grid[0])):
                if i == 0 and j == 0:
                    continue
                if i == 0:
                    self.dp[i][j] = self.dp[i][j - 1] + grid[i][j]
                elif j == 0:
                    self.dp[i][j] = self.dp[i-1][j] + grid[i][j]
                else:
                    self.dp[i][j] = min(self.dp[i-1][j],self.dp[i][j-1]) + grid[i][j]
        print(self.dp)
        return self.dp[len(grid) - 1][len(grid[0]) - 1]

if __name__ == "__main__":
    s = Solution()
    print(s.minPathSum([[1,3,1],[1,5,1],[4,2,1]]))